Search for: All records

We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments. 

Abstract Balancing kinetics, a crucial priority in catalysis, is frequently achieved by sacrificing activity of elementary steps to suppress side reactions and enhance catalyst stability. Dry reforming of methane (DRM), a process operated at high temperature, usually involves fast C-H activation but sluggish carbon removal, resulting in coke deposition and catalyst deactivation. Studies focused solely on catalyst innovation are insufficient in addressing coke formation efficiently. Herein, we develop coke-free catalysts that balance kinetics of elementary steps for overall thermodynamics optimization. Beginning from a highly active cobalt aluminum oxide (CoAl₂O₄) catalyst that is susceptible to severe coke formation, we substitute aluminum (Al) with gallium (Ga), reporting a CoAl_0.5Ga_1.5O₄-R catalyst that performs DRM stably over 1000 hours without observable coke deposition. We find that Ga enhances DRM stability by suppressing C-H activation to balance carbon removal. A series of coke-free DRM catalysts are developed herein by partially substituting Al from CoAl₂O₄with other metals. 

Wearable sensors are a topic of interest in medical healthcare monitoring due to their compact size and portability. However, providing power to the wearable sensors for continuous health monitoring applications is a great challenge. As the batteries are bulky and require frequent charging, the integration of the wireless power transfer (WPT) module into wearable and implantable sensors is a popular alternative. The flexible sensors benefit by being wirelessly powered, as it not only expands an individual’s range of motion, but also reduces the overall size and the energy needs. This paper presents the design, modeling, and experimental characterization of flexible square-shaped spiral coils with different scaling factors for WPT systems. The effects of coil scaling factor on inductance, capacitance, resistance, and the quality factor (Q-factor) are modeled, simulated, and experimentally validated for the case of flexible planar coils. The proposed analytical modeling is helpful to estimate the coil parameters without using the time-consuming Finite Element Method (FEM) simulation. The analytical modeling is presented in terms of the scaling factor to find the best-optimized coil dimensions with the maximum Q-factor. This paper also presents the effect of skin contact with the flexible coil in terms of the power transfer efficiency (PTE) to validate the suitability as a wearable sensor. The measurement results at 405 MHz show that when in contact with the skin, the 20 mm× 20 mm receiver (RX) coil achieves a 42% efficiency through the air media for a 10 mm distance between the transmitter (TX) and RX coils.